package com.sise.Backtracking;

import java.util.*;

/**
 *
 *      如果是一个集合来求组合的话，就需要 startIndex，因为一个集合中使用 startIndex 可以排除重复子集
 *      如果是多个集合取组合，各个集合之间相互不影响，那么就不用 startIndex
 *      注意以上我只是说求组合的情况，如果是排列问题，又是另一套分析的套路，后面我再讲解排列的时候就重点介绍。
 *
 *
 *      !!! 组合(39、40) 与 排列(46、47) 不同
 *      组合的结果集的数量并不确定，可能是 1、2、3个，例如：
 *      但排列的结果数量与 题目所要求的一样多(需要使用全部数字)，故此需要使用 used[] 判断其中的某个数字是否使用过，往往 i = 0 开始遍历循环开始
 *
 *
 *      39. 组合总和
 *
 *      给定一个无重复元素的数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。
 *      candidates 中的数字可以无限制重复被选取。
 *      所有数字（包括 target ）都是正整数。
 *      解集不能包含重复的组合。
 *
 *      输入：candidates = [2,3,6,7], target = 7,
 *      所求解集为：
 *      [
 *        [7],
 *        [2,2,3]
 *      ]
 *
 */
public class _39_combinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int length = candidates.length;
        List<List<Integer>> result = new ArrayList<>();
        if (length == 0) {
            return result;
        }

        Arrays.sort(candidates);
        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, length, target, path, result);       // begin 初始为0，说明所有的数值都可以选，假设 begin = 1，数组为 [1,2,3,4]，那么就只能选择 [2->4] 的数值
        return result;
    }

    private void dfs(int[] candidates, int begin, int length, int target, Deque<Integer> path, List<List<Integer>> result) {
        // 由于进入更深层的时候，小于 0 的部分被剪枝，因此递归终止条件值只判断等于 0 的情况
        if (target == 0) {
            result.add(new ArrayList<>(path));
            return;
        }

        // 这里的 i 代表的是 当前索引位置
        // 这里需要注意 i = begin，也就是说 以前使用过的值，现在就不可以使用了，因为以前的遍历就已经会覆盖所有的情况
        for (int i = begin; i < length; i++) {
            // 如果小于0，那么就剪枝
            if (target - candidates[i] < 0) {
                break;
            }

            path.addLast(candidates[i]);

            // 根据题意可知，每个数字可以重复使用多次，故此这里并没有进行 i++，而是使用 target 减去当前数值，故此会有 [2,2,3] 的情况
            dfs(candidates, i, length, target - candidates[i], path, result);
            path.removeLast();
        }
    }
}
